package com.wdc.binarytree;

import java.util.LinkedList;

/**
 * leetcode938 二叉搜索树的范围和
 */
public class E06Leetcode938 {

    public int rangeSumBST(TreeNode root, int low, int high) {
        TreeNode node = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        int sum = 0;
        while (node != null || !stack.isEmpty()){
            if (node != null){
                stack.push(node);
                node = node.left;
            }else {
                TreeNode pop = stack.pop();

                if (pop.val >= low && pop.val <= high){
                    sum += pop.val;
                }

                node = pop.right;
            }

        }
        return sum;
    }


    public int rangeSumBST1(TreeNode root, int low, int high) {

        if (root == null){
            return 0;
        }
        if (root.val < low){
            return rangeSumBST1(root.right,low,high);
        }
        if (root.val > high){
            return rangeSumBST1(root.left,low,high);
        }

        return root.val + rangeSumBST1(root.left,low,high) + rangeSumBST1(root.right,low,high);
    }
}
